
/* ====================================================================
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2002 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation" and
 *    "Apache POI" must not be used to endorse or promote products
 *    derived from this software without prior written permission. For
 *    written permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 *    "Apache POI", nor may "Apache" appear in their name, without
 *    prior written permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */

package org.apache.poi.util;

import java.util.*;

/**
 * A List of short's; as full an implementation of the java.util.List
 * interface as possible, with an eye toward minimal creation of
 * objects
 *
 * the mimicry of List is as follows:
 * <ul>
 * <li> if possible, operations designated 'optional' in the List
 *      interface are attempted
 * <li> wherever the List interface refers to an Object, substitute
 *      short
 * <li> wherever the List interface refers to a Collection or List,
 *      substitute ShortList
 * </ul>
 *
 * the mimicry is not perfect, however:
 * <ul>
 * <li> operations involving Iterators or ListIterators are not
 *      supported
 * <li> remove(Object) becomes removeValue to distinguish it from
 *      remove(short index)
 * <li> subList is not supported
 * </ul>
 *
 * @author Marc Johnson
 */

public class ShortList
{
    private short[]          _array;
    private int              _limit;
    private static final int _default_size = 128;

    /**
     * create an ShortList of default size
     */

    public ShortList()
    {
        this(_default_size);
    }

    /**
     * create a copy of an existing ShortList
     *
     * @param list the existing ShortList
     */

    public ShortList(final ShortList list)
    {
        this(list._array.length);
        System.arraycopy(list._array, 0, _array, 0, _array.length);
        _limit = list._limit;
    }

    /**
     * create an ShortList with a predefined initial size
     *
     * @param initialCapacity the size for the internal array
     */

    public ShortList(final int initialCapacity)
    {
        _array = new short[ initialCapacity ];
        _limit = 0;
    }

    /**
     * add the specfied value at the specified index
     *
     * @param index the index where the new value is to be added
     * @param value the new value
     *
     * @exception IndexOutOfBoundsException if the index is out of
     *            range (index < 0 || index > size()).
     */

    public void add(final int index, final short value)
    {
        if (index > _limit)
        {
            throw new IndexOutOfBoundsException();
        }
        else if (index == _limit)
        {
            add(value);
        }
        else
        {

            // index < limit -- insert into the middle
            if (_limit == _array.length)
            {
                growArray(_limit * 2);
            }
            System.arraycopy(_array, index, _array, index + 1,
                             _limit - index);
            _array[ index ] = value;
            _limit++;
        }
    }

    /**
     * Appends the specified element to the end of this list
     *
     * @param value element to be appended to this list.
     *
     * @return true (as per the general contract of the Collection.add
     *         method).
     */

    public boolean add(final short value)
    {
        if (_limit == _array.length)
        {
            growArray(_limit * 2);
        }
        _array[ _limit++ ] = value;
        return true;
    }

    /**
     * Appends all of the elements in the specified collection to the
     * end of this list, in the order that they are returned by the
     * specified collection's iterator.  The behavior of this
     * operation is unspecified if the specified collection is
     * modified while the operation is in progress.  (Note that this
     * will occur if the specified collection is this list, and it's
     * nonempty.)
     *
     * @param c collection whose elements are to be added to this
     *          list.
     *
     * @return true if this list changed as a result of the call.
     */

    public boolean addAll(final ShortList c)
    {
        if (c._limit != 0)
        {
            if ((_limit + c._limit) > _array.length)
            {
                growArray(_limit + c._limit);
            }
            System.arraycopy(c._array, 0, _array, _limit, c._limit);
            _limit += c._limit;
        }
        return true;
    }

    /**
     * Inserts all of the elements in the specified collection into
     * this list at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements
     * to the right (increases their indices).  The new elements will
     * appear in this list in the order that they are returned by the
     * specified collection's iterator.  The behavior of this
     * operation is unspecified if the specified collection is
     * modified while the operation is in progress.  (Note that this
     * will occur if the specified collection is this list, and it's
     * nonempty.)
     *
     * @param index index at which to insert first element from the
     *              specified collection.
     * @param c elements to be inserted into this list.
     *
     * @return true if this list changed as a result of the call.
     *
     * @exception IndexOutOfBoundsException if the index is out of
     *            range (index < 0 || index > size())
     */

    public boolean addAll(final int index, final ShortList c)
    {
        if (index > _limit)
        {
            throw new IndexOutOfBoundsException();
        }
        if (c._limit != 0)
        {
            if ((_limit + c._limit) > _array.length)
            {
                growArray(_limit + c._limit);
            }

            // make a hole
            System.arraycopy(_array, index, _array, index + c._limit,
                             _limit - index);

            // fill it in
            System.arraycopy(c._array, 0, _array, index, c._limit);
            _limit += c._limit;
        }
        return true;
    }

    /**
     * Removes all of the elements from this list.  This list will be
     * empty after this call returns (unless it throws an exception).
     */

    public void clear()
    {
        _limit = 0;
    }

    /**
     * Returns true if this list contains the specified element.  More
     * formally, returns true if and only if this list contains at
     * least one element e such that o == e
     *
     * @param o element whose presence in this list is to be tested.
     *
     * @return true if this list contains the specified element.
     */

    public boolean contains(final short o)
    {
        boolean rval = false;

        for (int j = 0; !rval && (j < _limit); j++)
        {
            if (_array[ j ] == o)
            {
                rval = true;
            }
        }
        return rval;
    }

    /**
     * Returns true if this list contains all of the elements of the
     * specified collection.
     *
     * @param c collection to be checked for containment in this list.
     *
     * @return true if this list contains all of the elements of the
     *         specified collection.
     */

    public boolean containsAll(final ShortList c)
    {
        boolean rval = true;

        if (this != c)
        {
            for (int j = 0; rval && (j < c._limit); j++)
            {
                if (!contains(c._array[ j ]))
                {
                    rval = false;
                }
            }
        }
        return rval;
    }

    /**
     * Compares the specified object with this list for equality.
     * Returns true if and only if the specified object is also a
     * list, both lists have the same size, and all corresponding
     * pairs of elements in the two lists are equal.  (Two elements e1
     * and e2 are equal if e1 == e2.)  In other words, two lists are
     * defined to be equal if they contain the same elements in the
     * same order.  This definition ensures that the equals method
     * works properly across different implementations of the List
     * interface.
     *
     * @param o the object to be compared for equality with this list.
     *
     * @return true if the specified object is equal to this list.
     */

    public boolean equals(final Object o)
    {
        boolean rval = this == o;

        if (!rval && (o != null) && (o.getClass() == this.getClass()))
        {
            ShortList other = ( ShortList ) o;

            if (other._limit == _limit)
            {

                // assume match
                rval = true;
                for (int j = 0; rval && (j < _limit); j++)
                {
                    rval = _array[ j ] == other._array[ j ];
                }
            }
        }
        return rval;
    }

    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of element to return.
     *
     * @return the element at the specified position in this list.
     *
     * @exception IndexOutOfBoundsException if the index is out of
     *            range (index < 0 || index >= size()).
     */

    public short get(final int index)
    {
        if (index >= _limit)
        {
            throw new IndexOutOfBoundsException();
        }
        return _array[ index ];
    }

    /**
     * Returns the hash code value for this list.  The hash code of a
     * list is defined to be the result of the following calculation:
     *
     * <code>
     * hashCode = 1;
     * Iterator i = list.iterator();
     * while (i.hasNext()) {
     *      Object obj = i.next();
     *      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
     * }
     * </code>
     *
     * This ensures that list1.equals(list2) implies that
     * list1.hashCode()==list2.hashCode() for any two lists, list1 and
     * list2, as required by the general contract of Object.hashCode.
     *
     * @return the hash code value for this list.
     */

    public int hashCode()
    {
        int hash = 0;

        for (int j = 0; j < _limit; j++)
        {
            hash = (31 * hash) + _array[ j ];
        }
        return hash;
    }

    /**
     * Returns the index in this list of the first occurrence of the
     * specified element, or -1 if this list does not contain this
     * element.  More formally, returns the lowest index i such that
     * (o == get(i)), or -1 if there is no such index.
     *
     * @param o element to search for.
     *
     * @return the index in this list of the first occurrence of the
     *         specified element, or -1 if this list does not contain
     *         this element.
     */

    public int indexOf(final short o)
    {
        int rval = 0;

        for (; rval < _limit; rval++)
        {
            if (o == _array[ rval ])
            {
                break;
            }
        }
        if (rval == _limit)
        {
            rval = -1;   // didn't find it
        }
        return rval;
    }

    /**
     * Returns true if this list contains no elements.
     *
     * @return true if this list contains no elements.
     */

    public boolean isEmpty()
    {
        return _limit == 0;
    }

    /**
     * Returns the index in this list of the last occurrence of the
     * specified element, or -1 if this list does not contain this
     * element.  More formally, returns the highest index i such that
     * (o == get(i)), or -1 if there is no such index.
     *
     * @param o element to search for.
     *
     * @return the index in this list of the last occurrence of the
     *         specified element, or -1 if this list does not contain
     *         this element.
     */

    public int lastIndexOf(final short o)
    {
        int rval = _limit - 1;

        for (; rval >= 0; rval--)
        {
            if (o == _array[ rval ])
            {
                break;
            }
        }
        return rval;
    }

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from
     * their indices).  Returns the element that was removed from the
     * list.
     *
     * @param index the index of the element to removed.
     *
     * @return the element previously at the specified position.
     *
     * @exception IndexOutOfBoundsException if the index is out of
     *            range (index < 0 || index >= size()).
     */

    public short remove(final int index)
    {
        if (index >= _limit)
        {
            throw new IndexOutOfBoundsException();
        }
        short rval = _array[ index ];

        System.arraycopy(_array, index + 1, _array, index, _limit - index);
        _limit--;
        return rval;
    }

    /**
     * Removes the first occurrence in this list of the specified
     * element (optional operation).  If this list does not contain
     * the element, it is unchanged.  More formally, removes the
     * element with the lowest index i such that (o.equals(get(i)))
     * (if such an element exists).
     *
     * @param o element to be removed from this list, if present.
     *
     * @return true if this list contained the specified element.
     */

    public boolean removeValue(final short o)
    {
        boolean rval = false;

        for (int j = 0; !rval && (j < _limit); j++)
        {
            if (o == _array[ j ])
            {
                System.arraycopy(_array, j + 1, _array, j, _limit - j);
                _limit--;
                rval = true;
            }
        }
        return rval;
    }

    /**
     * Removes from this list all the elements that are contained in
     * the specified collection
     *
     * @param c collection that defines which elements will be removed
     *          from this list.
     *
     * @return true if this list changed as a result of the call.
     */

    public boolean removeAll(final ShortList c)
    {
        boolean rval = false;

        for (int j = 0; j < c._limit; j++)
        {
            if (removeValue(c._array[ j ]))
            {
                rval = true;
            }
        }
        return rval;
    }

    /**
     * Retains only the elements in this list that are contained in
     * the specified collection.  In other words, removes from this
     * list all the elements that are not contained in the specified
     * collection.
     *
     * @param c collection that defines which elements this set will
     *          retain.
     *
     * @return true if this list changed as a result of the call.
     */

    public boolean retainAll(final ShortList c)
    {
        boolean rval = false;

        for (int j = 0; j < _limit; )
        {
            if (!c.contains(_array[ j ]))
            {
                remove(j);
                rval = true;
            }
            else
            {
                j++;
            }
        }
        return rval;
    }

    /**
     * Replaces the element at the specified position in this list
     * with the specified element
     *
     * @param index index of element to replace.
     * @param element element to be stored at the specified position.
     *
     * @return the element previously at the specified position.
     *
     * @exception IndexOutOfBoundsException if the index is out of
     *            range (index < 0 || index >= size()).
     */

    public short set(final int index, final short element)
    {
        if (index >= _limit)
        {
            throw new IndexOutOfBoundsException();
        }
        short rval = _array[ index ];

        _array[ index ] = element;
        return rval;
    }

    /**
     * Returns the number of elements in this list. If this list
     * contains more than Integer.MAX_VALUE elements, returns
     * Integer.MAX_VALUE.
     *
     * @return the number of elements in this ShortList
     */

    public int size()
    {
        return _limit;
    }

    /**
     * Returns an array containing all of the elements in this list in
     * proper sequence.  Obeys the general contract of the
     * Collection.toArray method.
     *
     * @return an array containing all of the elements in this list in
     *         proper sequence.
     */

    public short [] toArray()
    {
        short[] rval = new short[ _limit ];

        System.arraycopy(_array, 0, rval, 0, _limit);
        return rval;
    }

    /**
     * Returns an array containing all of the elements in this list in
     * proper sequence.  Obeys the general contract of the
     * Collection.toArray(Object[]) method.
     *
     * @param a the array into which the elements of this list are to
     *          be stored, if it is big enough; otherwise, a new array
     *          is allocated for this purpose.
     *
     * @return an array containing the elements of this list.
     */

    public short [] toArray(final short [] a)
    {
        short[] rval;

        if (a.length == _limit)
        {
            System.arraycopy(_array, 0, a, 0, _limit);
            rval = a;
        }
        else
        {
            rval = toArray();
        }
        return rval;
    }

    private void growArray(final int new_size)
    {
        int     size      = (new_size == _array.length) ? new_size + 1
                                                        : new_size;
        short[] new_array = new short[ size ];

        System.arraycopy(_array, 0, new_array, 0, _limit);
        _array = new_array;
    }
}   // end public class ShortList

